import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description: 二叉树
 * User:岁亮亮
 * Date:2024-06-04
 * TIME:19:01
 */
public class BinaryTree {

    public Node head;
    public int size;
    public BinaryTree(char value){
        head = new Node(value);
    }

    class Node{
        char value;
        Node leftNode;
        Node rightNode;
        public Node(char value){
            this.value = value;
        }
    }
    public void create(){
        /*Node node1 = new Node(1);
        Node node2= new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);
        head.leftNode = node1;
        head.rightNode = node2;
        node1.leftNode = node3;
        node1.rightNode = node4;
        node2.leftNode = node5;
        node2.rightNode = node6;
        node3.leftNode = node7;
        node3.rightNode = node8;
        node4.leftNode = node9;*/
    }
    public void preOrder(Node head){
        Node cur = head;
        if(cur == null){
            return;
        }
        System.out.print(cur.value+" ");
        preOrder(cur.leftNode);
        preOrder(cur.rightNode);
    }
    public List<Character> list = new ArrayList<>();
    public List<Character> preOrder2(Node head){
        Node cur = head;
        if(cur == head){
            return list;
        }
        list.add(cur.value);
        preOrder2(cur.leftNode);
        preOrder2(cur.rightNode);
        return list;
    }
    //子问题的思路 即用到返回值
    public List<Character> preOrder3(Node head){
        List<Character> list1 = new ArrayList<>();
        Node cur = head;
        if(cur == null){
            return list1;
        }
        list1.add(cur.value);
        List<Character> list2 = preOrder3(cur.leftNode);
        list1.addAll(list2);
        List<Character> list3 = preOrder3(cur.rightNode);
        list1.addAll(list3);
        return list1;
    }

    public void inOrder(Node head){
        Node cur = head;
        if(cur == null){
            return;
        }
        inOrder(cur.leftNode);
        System.out.print(cur.value + " ");
        inOrder(cur.rightNode);
    }

    public void postOrder(Node head){
        Node cur = head;
        if(cur == null){
            return;
        }
        postOrder(cur.leftNode);
        postOrder(cur.rightNode);
        System.out.print(cur.value + " ");
    }

    /***
     * 层序遍历
     * 借助队列 从上倒下 从左到右 依次遍历二叉树
     * 出一个元素 就把这个元素的左右节点入队
     * @param head
     */

    public void levelNode(Node head){
        if(head == null){
            return;
        }
        Queue<Node> queue = new LinkedList();
        queue.offer(head);
        while (!queue.isEmpty()){
            Node cur = queue.poll();
            System.out.println(cur.value + " ");
            if(cur.leftNode != null){
                queue.offer(cur.leftNode);
            }
            if(cur.rightNode != null){
                queue.offer(cur.rightNode);
            }
        }

    }
    public List<List<Character>> levelNode2(Node head){
        List<List<Character>> lists = new ArrayList<>();
        if(head == null){
            return lists;
        }
        Queue<Node> queue = new LinkedList();
        queue.offer(head);
        while (!queue.isEmpty()){
            List<Character> list1 = new ArrayList<>();
            int size = queue.size();
            while (size!=0){
                Node cur = queue.poll();
                list1.add(cur.value);
                size--;
                if(cur.leftNode != null){
                    queue.offer(cur.leftNode);
                }
                if(cur.rightNode != null){
                    queue.offer(cur.rightNode);
                }
            }
           lists.add(list1);
        }
        return lists;
    }


    /***
     * 根据先序遍历创建二叉树
     * @param str 字符串中
     * @return
     */
    // i 不能是私有变量 每次递归调用i时是上次i的下一位
     public static int i = 0;

    public Node createTree(String str){
        //先遍历字符串
        Node root = null;
        if(str.charAt(i) !='#'){
            root = new Node(str.charAt(i));
            i++;
            root.leftNode = createTree(str);
            root.rightNode = createTree(str);
        }
        else {
            i++;
        }
        return root;

        //2 根据前序遍历创建字符串

        //3返回根节点
    }

    int size(Node head){
        Node cur = head;
        if(head == null){
            return 0;
        }
        size++;
        size(cur.leftNode);
        size(cur.rightNode);
        return size;
    }
    int size2(Node head){
        Node cur = head;
        if(head == null){
            return 0;
        }
        int size1 = size2(cur.leftNode);
        int size2 = size2(cur.rightNode);
        return size1 + size2 + 1;
        /***
         * 或者 return size2(cur.leftNode)+ size2(cur.rightNode)+ 1;
         */
    }

    int getLeafNode(Node head){
        Node cur = head;
        if(cur == null){
            return 0;
        }
        if(cur.leftNode == null && cur.rightNode == null){
            return 1;
        }
        return getLeafNode(cur.leftNode) + getLeafNode(cur.rightNode);
    }

    /***
     * 获取第 k 层结点的个数
     * 就是获取根节点左子树的第k-1层 加 根节点右子树的第k-1层
     * 依次类推到k=1层的所有节点之和 就是第k层的节点的个数
     * @param head
     * @param k
     * @return
     */
    int getLevelNodeCount(Node head,int k){
        if(head == null){
            return 0;
        }
        if(k==1 ){
            return 1;
        }
        return getLevelNodeCount(head.leftNode,k-1)+getLevelNodeCount(head.rightNode,k-1);


    }
    //得到树的高度 左右子树的高度最大值加一
    int getTreeLength(Node head){
        if(head == null){
            return 0;
        }
        int size1 = getTreeLength(head.leftNode);
        int size2 = getTreeLength(head.rightNode);
        return size1 > size2 ? size1 + 1 : size2 + 1;

    }
   //判断是否存在 value ==target的节点
    boolean findNode(Node head,int target){
        if(head == null){
            return false;
        }
        if(head.value == target){
            return true;
        }
        boolean left = findNode(head.leftNode,target);
        if(left == true){
            return true;
        }
        boolean right = findNode(head.rightNode,target);
        if(right == true){
            return true;
        }
        return false;

    }
    /***
     *  判断两棵树是否相同
     *  1.结构上进行判断
     *  节点的值的判断
     *  2.遍历树比较value 是否相同
     */
    boolean isSameTree(Node cur1,Node cur2){
        if((cur1 == null && cur2 != null) || (cur1 != null && cur2 == null)){
            return false;
        }
        if(cur1 == null && cur2 == null){
            return true;
        }
        if(cur1.value != cur2.value){
            return false;
        }
        return isSameTree(cur1.leftNode,cur2.leftNode)&&isSameTree(cur1.rightNode,cur2.rightNode);

    }

    /***
     * 时间的复杂度O(M*N)
     * 判断subroot 是否是 root 的子树
     * 1.判断根节点是否相同
     * 2.再判断左右子树是否相同
     * 3.都不相同返回false
     * @param root
     * @param subRoot
     * @return
     */
    public boolean isSubtree(Node root, Node subRoot) {
        if(isSameTree(root,subRoot)){
            return true;
        }
        if(root == null){
            return false;
        }
        if(isSubtree(root.leftNode,subRoot)){
            return true;
        }
        if(isSubtree(root.rightNode,subRoot)){
            return true;
        }
        return false;

    }
    /***
     * 翻转二叉树
     */
    public Node reserveBinaryTree(Node head){
        if(head == null){
            return head;
        }

        Node reserve = head.leftNode;
        head.leftNode = head.rightNode;
        head.rightNode = reserve;

        reserveBinaryTree(head.leftNode);
        reserveBinaryTree(head.rightNode);
        return head;

    }
    /***
     * 翻转等价二叉树
     * 给定两个二叉树 判断让root2 的左右子树翻转 能使root1 == root2
     */
    public boolean eaquivalenceTree(Node root1,Node root2){
        if(root1 == root2){
            return  true;
        }
        if(root1 == null || root2 == null|| root1.value != root2.value){
            return  false;
        }
        return eaquivalenceTree(root1.leftNode,root2.leftNode)&&eaquivalenceTree(root1.rightNode,root2.rightNode)||
                eaquivalenceTree(root1.leftNode,root2.rightNode)&&eaquivalenceTree(root1.rightNode,root2.leftNode);
    }
    /***
     * 一棵树是否对称
     */
    public boolean isSymmetric(Node head){
        if(head == null){
            return true;
        }
        return isSymmetricChild(head.leftNode,head.rightNode);

    }
    public boolean isSymmetricChild(Node leftNode,Node rightNode){
        if(leftNode == rightNode){
            return true;
        }
        if(leftNode == null || rightNode == null || leftNode.value != rightNode.value){
            return false;
        }
        return isSymmetricChild(leftNode.leftNode,rightNode.rightNode)&&isSymmetricChild(leftNode.rightNode,rightNode.leftNode);

    }


    /***
     * 判断平衡二叉树两种写法
     * 1.O(N*N)
     * 先求这棵树的左右子树节点的高度 再 比较左右子树的高度相减绝对值小于等于1以及 递归 这棵树的左右子树是否平衡
     * 求完高度 再进行左右子树的高度差 再进行这颗子树的左右子树是否平衡
     * 2.O(N)
     * 在求这棵树的左右子树的高度  时 比较左右子树的高度差是否小于等于1 若小于直接返回一个负数表示这棵树是不平衡的
     * 在求整棵树的高度时 进行左右子树的高度差的比较 若有子树返回负数则这棵树是不平衡的
     */
    public boolean isBalanced(Node head){
        if(head == null){
            return true;
        }
        int leftSize = getTreeLength(head.leftNode);
        int rightSize = getTreeLength(head.rightNode);
        return Math.abs(leftSize - rightSize) <= 1 &&isBalanced(head.leftNode)&&isBalanced(head.rightNode);
    }
    public boolean isBalanced2(Node head){
        if(head == null){
            return true;
        }
        return getTreeLength2(head) >= 0;

    }
    public int getTreeLength2(Node head){
        if(head == null){
            return 0;
        }
        if(head.leftNode == null && head.rightNode == null){
            return 1;
        }
        int leftSize = getTreeLength2(head.leftNode);
        if(leftSize < 0){
            return -1;
        }
        int rightSize = getTreeLength2(head.rightNode);
        if(leftSize >= 0 && rightSize >= 0 && Math.abs(leftSize - rightSize)<=1){
            return leftSize > rightSize ? leftSize + 1 : rightSize + 1;
        }
        else {
            return -1;
        }
    }

    /***
     * 判断是否是完全二叉树
     * 首先用队列层序遍历二叉树 若遇到null 时 退出循环
     * 再判断队列中是否存在非 null 的元素 有返回false
     */
    public boolean isCompleteTree(Node head){
        if(head == null){
            return true;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(head);
        while (!queue.isEmpty()){
            Node cur = queue.poll();
            if(cur != null){
                queue.offer(cur.leftNode);
                queue.offer(cur.rightNode);
            }
            else {
                break;
            }
        }
        while (!queue.isEmpty()){
            Node cur = queue.peek();
            if(cur != null){
                queue.poll();
            }
            else {
                return false;
            }
        }
        return true;

    }






}
